<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head>


<title>Sphere Online Judge (SPOJ)  - Problem MICEMAZE</title>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-2" id="metatag">
<meta name="Keywords" content="programming, language, algorithm, spoj, contest, contester, Java, C#, Pascal, C, C++, python, ruby, caml, ocaml, perl, haskell, lisp, prolog, fortran, assembler, asembler, functional, online, judge, problem, problemset, ACM">

<link href="https://www.spoj.pl/gfx/favicon.png" rel="shortcut icon" type="image/x-icon">
<link href="https://www.spoj.pl/rss/" rel="alternate" type="application/rss+xml" title="RSS Feed">
<link href="spoj-01845_files/style.css" rel="stylesheet" type="text/css" id="theme">
<link href="spoj-01845_files/tooltips.css" rel="stylesheet" type="text/css" id="theme">
<script type="text/javascript" src="spoj-01845_files/jquery_003.js"></script>
<style type="text/css">
<!--
.maintable {width: 755px;} 
-->
</style>
<script type="text/javascript" language="javascript">
<!--
function UnCryptMailto(s) {
	var n=0;
	var r="";
	for(var i=0;i<s.length;i++) {		
		n=s.charCodeAt(i); 
		if (n>=8364) {n = 128;}
		r += String.fromCharCode(n+(2));	
	}
	return r;
}
function linkTo_UnCryptMailto(s)	{
	location.href=UnCryptMailto(s);
}
// -->
</script>

</head><body>
<center>
<table class="maintable" id="maintable" cellpadding="10" cellspacing="0">
<tbody><tr>
    <td colspan="2" class="header">
        <table border="0" cellpadding="0" cellspacing="0" width="100%">
        <tbody><tr>
		<td class="headerleft">
		</td><td class="headercenter">
<h1><img alt="Sphere Online Judge" title="Sphere Online Judge" src="spoj-01845_files/sphere-spoj-small.png" style="margin-top: -4px; margin-bottom: -4px;" border="0"></h1>
		</td>
		<td class="headerright">
	</td></tr>
	</tbody></table>
    </td>
</tr>
<tr><td class="menu" valign="top" width="92">


<div class="menucmd"><a href="https://www.spoj.pl/logout"><b style="font-weight: normal;">Log Out</b></a><br><b style="font-weight: normal; margin-right: -100px;">dncampo</b><br><hr><a href="https://www.spoj.pl/myaccount">my account</a><br><a href="https://www.spoj.pl/tutorials">tutorials</a><br><br><a href="https://www.spoj.pl/status">status</a><br><a href="https://www.spoj.pl/submit">submit</a><br><a href="https://www.spoj.pl/problems/classical/">problems</a><br><a href="https://www.spoj.pl/search">search</a><br><br><a href="https://www.spoj.pl/">news</a><br><a href="https://www.spoj.pl/contests">contests</a><br><a href="https://www.spoj.pl/ranks/">ranks</a><br><br><a href="https://www.spoj.pl/forum">forum</a><br><a href="https://www.spoj.pl/comments">comments</a><br><a href="https://www.spoj.pl/credits">credits</a><br><hr></div><a href="https://www.spoj.pl/problems/classical/"></a><br>

	<div class="time">
Server time:</div>
<div class="time">
2009-09-02
<br>
<b>06 : 12 : 14</b>
</div>

</td>
<td style="padding: 0px;" class="content0" valign="top">
        <table cellpadding="0" cellspacing="0" width="100%">
        <tbody><tr>
                <td style="padding: 0px;" colspan="2"><center>
                                
                </center></td>
        </tr>
        <tr>
                <td class="content" style="padding: 10px;" width="99%">
	<script type="text/javascript" src="spoj-01845_files/jquery_002.js"></script>
<script type="text/javascript" src="spoj-01845_files/jquery.js"></script>
<script type="text/javascript" src="spoj-01845_files/jquery_004.js"></script>


	 <!-- wykorzystywane w pcontent.html (by wiele) -->
	
	<table class="problems" width="100%">
	<tbody><tr class="navigation">
			<td><a href="https://www.spoj.pl/submit/MICEMAZE/">Submit</a></td>
			<td><a href="https://www.spoj.pl/status/MICEMAZE,dncampo/">My submissions</a></td>
		<td><a href="https://www.spoj.pl/status/MICEMAZE/">All submissions</a></td>
	<td><a href="https://www.spoj.pl/ranks/MICEMAZE/">Best solutions</a></td>
	<td><a href="https://www.spoj.pl/problems/MICEMAZE.ps">PS</a></td>
	<td><a href="https://www.spoj.pl/problems/MICEMAZE.pdf">PDF</a></td>
	<td><a href="https://www.spoj.pl/problems/classical/">Back to list</a></td>
	</tr>
	</tbody></table>

	<div class="prob">


	<!-- plik z pomoca kontekstowa (cxhelp_*) dziedziczony po pindex.html -->


<table style="margin-top: 10px;" width="100%">
<tbody><tr>
	<td>
		<h2>SPOJ Problem Set (classical)</h2>
		<h1>1845. Mice and Maze</h1>
		<h2>Problem code: MICEMAZE</h2>
	</td>
	</tr>
</tbody></table>

<p align="justify">
</p><p align="justify">
A set of laboratory mice is being trained to escape a maze. 
The maze is made up of cells, and each cell is
connected to some other cells. 
However, there are obstacles in the passage between
cells and therefore there is a time penalty to overcome the passage
Also, some passages allow mice to go one-way,
but not the other way round.

</p><p align="justify">
Suppose that all mice are now trained and,  when placed  in  an  arbitrary
cell in the maze, take a path that leads them to  the  exit cell in minimum
time.

</p><p align="justify">
We are going to conduct the following experiment: 
a mouse is placed in each cell  of
the maze and a count-down timer is started.
When the timer stops we count the number of mice out of the maze.

<font color="#0000ff"><h2>Problem</h2></font>

</p><p align="justify">
Write a program that, given a description of the maze and the time limit,
predicts the number of mice that will exit the maze. Assume
that there are no bottlenecks is the maze, i.e. that all cells have
room for an arbitrary number of mice.

</p><h3>Input</h3>

<p align="justify">
The maze cells are numbered <img src="spoj-01845_files/overwiseaimg1.gif" alt="$1,2,\ldots,N$" align="middle" border="0" width="84" height="32">, where <img src="spoj-01845_files/overwiseaimg2.gif" alt="$N$" align="bottom" border="0" width="20" height="15"> is the total number
of cells. You can assume that <img src="spoj-01845_files/overwiseaimg3.gif" alt="$N\leq 100$" align="middle" border="0" width="70" height="32">.

</p><p align="justify">
The first three input lines contain 
<img src="spoj-01845_files/overwiseaimg2.gif" alt="$N$" align="bottom" border="0" width="20" height="15">, the number of cells in the
maze, <img src="spoj-01845_files/overwiseaimg4.gif" alt="$E$" align="bottom" border="0" width="18" height="15">, the number of the exit cell,
and the starting value <img src="spoj-01845_files/overwiseaimg5.gif" alt="$T$" align="bottom" border="0" width="17" height="15"> for the count-down timer 
(in some arbitrary time unit).

</p><p align="justify">
The fourth line contains the number <img src="spoj-01845_files/overwiseaimg6.gif" alt="$M$" align="bottom" border="0" width="23" height="15"> of 
connections in the maze, and is followed by <img src="spoj-01845_files/overwiseaimg6.gif" alt="$M$" align="bottom" border="0" width="23" height="15"> lines,
each specifying a connection
with three integer numbers: two cell numbers <img src="spoj-01845_files/overwiseaimg7.gif" alt="$a$" align="bottom" border="0" width="14" height="16"> and <img src="spoj-01845_files/overwiseaimg8.gif" alt="$b$" align="bottom" border="0" width="12" height="16">
(in the range <img src="spoj-01845_files/overwiseaimg9.gif" alt="$1,\ldots,N$" align="middle" border="0" width="68" height="32">) and the number of time units
it takes to travel from <img src="spoj-01845_files/overwiseaimg7.gif" alt="$a$" align="bottom" border="0" width="14" height="16"> to <img src="spoj-01845_files/overwiseaimg8.gif" alt="$b$" align="bottom" border="0" width="12" height="16">.

</p><p align="justify">
Notice that each connection is one-way, i.e., 
the mice can't travel from <img src="spoj-01845_files/overwiseaimg8.gif" alt="$b$" align="bottom" border="0" width="12" height="16"> to <img src="spoj-01845_files/overwiseaimg7.gif" alt="$a$" align="bottom" border="0" width="14" height="16">
unless there is another line specifying that passage.
Notice also that the time required
to travel in each direction might be different.

</p><h3>Output</h3>

<p align="justify">
The output consists of a single line with 
the number of mice that reached the exit cell <img src="spoj-01845_files/overwiseaimg4.gif" alt="$E$" align="bottom" border="0" width="18" height="15"> in at
most <img src="spoj-01845_files/overwiseaimg5.gif" alt="$T$" align="bottom" border="0" width="17" height="15"> time units.

</p><h3>Example</h3>

<pre><b>Input:</b>
4 
2 
1
8
1 2 1
1 3 1
2 1 1
2 4 1
3 1 1
3 4 1
4 2 1
4 3 1

<b>Output:</b>
3
</pre>


<hr>
<table style="margin-bottom: 10px;" class="probleminfo" align="left" border="0" cellpadding="0" cellspacing="0">
<tbody><tr><td>Added by:</td><td><a href="https://www.spoj.pl/users/overwise">Robin Nittka</a></td></tr>
<tr><td>Date:</td><td>2007-10-04</td></tr>
<tr><td>Time limit:</td><td>2s
</td></tr>
<tr><td>Source limit:</td><td>50000B</td></tr>
<tr><td>Languages:</td><td>All </td></tr>
<tr><td>Resource:</td><td>ACM ICPC -- SWERC 2001</td></tr>
	
</tbody></table>
	<div id="ccontent">
	
<hr style="clear: both;">
<a href="#" onclick="toggleComments(); return false;"><span id="comments_sh">hide</span> comments</a><br>

<a id="comments"></a>
<table id="comments_table" width="100%">
		<tbody><tr>
		<td colspan="2">
				</td>
	</tr>
	
	<script language="JavaScript">
	<!--
	$(document).ready(function(){
        $('.pager_link').bind('click', function(me){
                var href=$(me.currentTarget).attr('href');
		$('#ccontent').animate({opacity: 0.5},1);
                $.ajax({
                        type: "GET",
                        url: href+",ajax=1",
                        contentType: "application/x-www-form-urlencoded;charset=ISO-8859-2",
                        success: function(data){
                                $('#ccontent').html(data);
				$('#ccontent').animate({opacity: 1.0},1);
                        },
                        error: function(err){
                                alert('error');
                        }
                });
                return false;
        });
	});
	-->
	</script>
	

			
	<tr>
		<td colspan="2" class="comm comm_odd">
		<font>
		2009-08-05 19:44:11 <b><a href="https://www.spoj.pl/users/david70">David Gomez</a></b> 
		</font>
								<br>
				Mice in positions 1, 2 and 4 reached the exit cell in at most 1 time units.
						</td>
	</tr>
				
	<tr>
		<td colspan="2" class="comm comm_even">
		<font>
		2009-07-11 22:01:25 <b><a href="https://www.spoj.pl/users/ashokvardhan">Ashok vardhan</a></b> 
		</font>
								<br>
				Can any one explain me how the output is 3...???
						</td>
	</tr>
			
</tbody></table>


<script language="javascript" type="text/javascript">
<!--
function getCookieVal (offset) {
        var endstr = document.cookie.indexOf (";", offset);
        if (endstr == -1) { 
                endstr = document.cookie.length; 
        }
        return unescape(document.cookie.substring(offset, endstr));
}

function GetCookie (name) {
  var arg = name + "=";
  var alen = arg.length;
  var clen = document.cookie.length;
  var i = 0;
  while (i < clen) {
    var j = i + alen;
    if (document.cookie.substring(i, j) == arg) {
      return getCookieVal (j);
      }
    i = document.cookie.indexOf(" ", i) + 1;
    if (i == 0) break; 
    }
  return null;
}

function toggleComments() {
        var a = document.getElementById('comments_table');
        var d = a.style.display;
        if( d == "" || d == "block" ){
                d = "none";
                document.getElementById('comments_sh').innerHTML = 'show';
        } else {
                d = "block";
                document.getElementById('comments_sh').innerHTML = 'hide';
        }
        a.style.display = d;
        document.cookie="comments_table="+d+"; path=/;";
}

if( GetCookie('comments_table') == 'none' ){
        document.getElementById('comments_sh').innerHTML = 'show';
        document.getElementById('comments_table').style.display = 'hide';
}

-->
</script>


	</div>
	<table width="100%">
                <tbody><tr>
                <td colspan="2" height="20"></td>
        </tr>
        <form method="post" action="/comment/MICEMAZE/add/"></form>
        <tr> <td style="padding-left: 5px;" colspan="2">Leave a Comment</td> </tr>
        <tr>
                <td valign="top"></td>
                <td><textarea name="content" cols="40" rows="3"></textarea></td>
        </tr>
                <tr>
                <td colspan="2" style="padding-left: 5px;">
                        <input value="Publish" type="submit">
                        <input name="pcode" value="MICEMAZE" type="hidden">
                </td>
        </tr>
<tr>
<td colspan="2" class="smallgrey" style="padding-left: 5px;">
Notes:
<br>1. Don't post any source code here.
<br>2. Please be careful, leave short comments only. Don't spam here.
<br>3. For more discussion (hints, ideas, solutions) please visit our <a href="https://www.spoj.pl/forum">forum</a>.
<br>4. Authors are allowed to delete the post and use html code here (e.g. to provide some useful links).
</td>
</tr>
        
        </tbody></table>

	</div>
        </td>
</tr><tr>
        <td style="padding: 0px;" colspan="2"><center>
                
</center></td>
</tr>
</tbody></table>
</td>
</tr>

<tr>
<td colspan="2" class="footer">

<script language="javascript" type="text/javascript">
<!--
function swapSheet(sheet, caller) {
    document.getElementById('theme').href=sheet;
    document.cookie="css_0="+sheet+"; path=/;";
    caller.href="#bottom";
}

function setWidth(w, caller) {
    document.getElementById('maintable').style.width=w;
    document.cookie="res="+w+"; path=/;";
    caller.href="#bottom";
}
//-->

</script>
        <table width="100%">
    <tbody><tr>
	<td class="cfooter" align="left" width="10%">
	<a href="https://www.spoj.pl/info/">About SPOJ</a>
	</td>
	<td class="cfooter" align="center">
	    page size:
	    <a href="https://www.spoj.pl/?rsl=755px" onclick="setWidth('755px', this)">800x600</a>
	    <a href="https://www.spoj.pl/?rsl=980px" onclick="setWidth('980px', this)">1024x768</a>
	    <a href="https://www.spoj.pl/?rsl=100%" onclick="setWidth('100%', this)">Full</a>
	    &nbsp;&nbsp;
	    theme:
	    <a href="https://www.spoj.pl/?css=/themes/skin1.css" onclick="swapSheet('/themes/skin1.css', this)">olive</a>
	    <a href="https://www.spoj.pl/?css=/themes/skin2.css" onclick="swapSheet('/themes/skin2.css', this)">banana</a>
	    <a href="https://www.spoj.pl/?css=/themes/skin3.css" onclick="swapSheet('/themes/skin3.css', this)">plum</a>
	</td>
		<td class="cfooter" align="center">
		 <span title="The discussion channel of the Sphere Online Judge community.">
		 <a href="irc://irc.freenode.net/spoj"><b>#spoj</b> at freenode</a>
		 </span>
	</td>
		<td class="cfooter" style="text-align: right;" width="10%">
		<a href="https://www.spoj.pl/rss/"><img src="spoj-01845_files/rss10x10.gif" border="0">&nbsp;RSS</a>&nbsp;
	
	</td>
    </tr>
    </tbody></table>
    </td></tr></tbody></table>
</center>
<div style="font-size: 10px; margin-top: 4px; color: rgb(85, 80, 95);"><center>
<a href="http://www.spoj.pl/" style="color: black;">SPOJ</a>
System &#169; 2008-2009
<a href="http://sphere-research.com/" style="color: black;">Sphere Research Labs</a>. 
All Rights Reserved.</center></div>
</body></html>